﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Sort
{
    /// <summary>
    ///  将待排序的序列中的元素按照大小插入到已排序的序列中
    ///  original: 7 1 3 9
    ///             [7] 1 3 9
    ///  first:     [1 7] 3 9   拿1出来插入前面序列
    ///  second:    [1 3 7] 9   拿3出来插入前面序列[1 7]
    /// 
    ///  时间复杂度 O(n*n)
    /// </summary>
    public class InsertSort
    {
        public int[] arrForSort = new int[100];

        public InsertSort(int[] arr)
        {
            this.arrForSort = arr;
        }

        public int[] Execute()
        {
            int i, j, temp;

            for (i = 1; i < arrForSort.Length; i++)
            {
                temp = arrForSort[i];

                for (j = i; j > 0 && temp < arrForSort[j-1]; j--)
                {
                    arrForSort[j] = arrForSort[j - 1];
                }

                arrForSort[j] = temp;
            }

            return arrForSort;
        }
    }
}
